class Solution3 {
    public List<Integer> countSmaller(int[] nums) {
        int len = nums.length;

        //辅助treeset数组，给nums排序去重
        TreeSet<Integer> set = new TreeSet<Integer>();
        for(int i : nums) {
            set.add(i);
        }

        //辅助map数组，储存nums按从小到大顺序的对应排序序号
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int index = 1;
        for(int seti : set) {
            map.put(seti, index++);
        }

        //树状数组
        FenwickTree tree = new FenwickTree(set.size() + 1);
        //最终返回结果数组
        List<Integer> result = new LinkedList<Integer>();
        for(int i = len - 1; i >= 0; i--) {
            tree.update(map.get(nums[i]), 1);
            result.add(tree.query(map.get(nums[i]) - 1));
        }

        Collections.reverse(result);
        return result;
    }

    private class FenwickTree {
        //树状数组
        int[] tree;
        int len;

        public FenwickTree(int len) { 
            this.len = len;
            this.tree = new int[len + 1];
        }

        public void update(int index, int input) {
            //向树状数组里面index节点增加input值，index的父节点也要增加同样的值
            while(index <= this.len) {
                tree[index] += input;
                index += lowbit(index);
            }
        }

        public int query(int index) {
            int result = 0;
            //查询树状数组index节点及之前所有项之和
            while(index > 0) {
                result += tree[index];
                index -= lowbit(index);
            }
            return result;
        }

        public int lowbit(int i) {
            //取二进制数i最右边的1及后面的0
            return i & (-i);
        }
    }
}